#include <iostream>
#include <vector>

using namespace std;

/**
 * @brief The Solution class 131 分割回文串
 */
class Solution
{
public:
    explicit Solution(): result(){}
private:
    vector<vector<string>> result;
    vector<vector<int>> f;
public:
    // 格式化代码： ctrol + i
    vector<vector<string>> partition(const string &s)
    {
        int n = s.size();
        f.assign(n,vector<int>(n,0)); // 记忆法，判断字符串是否为回文数

        vector<string> path;
        dfs(path, s, 0);
        return result;
    }


private:

    /**
     * @brief isCorrect 判断是否为回文数
     * @param s 字符串
     * @param i 起始下标（包含）
     * @param j 结束下标（包含）
     * @return 1=是回文数 -1=非回文数 0=未检查过
     */
    int isCorrect(const string& s, int i, int j)
    {
        if(f[i][j])
        {
            return f[i][j];
        }

        if(i >= j)
        {
            // 一个元素时，算是回文数
            // 空元素时
            return 1;
        }

        if(s[i] == s[j])
        {
            f[i][j] = isCorrect(s,i+1,j-1);
            return f[i][j];
        }

        f[i][j] = -1;
        return f[i][j];
    }

    void dfs(vector<string>& path,
             const string& str, int i)
    {
        int n = str.size();
        if(i >= n)
        {
            result.push_back(path); // 操作路径拷贝到结果中去

            int pos = 0;
            printf("[");
            for(const string& s: path)
            {
                if(pos != 0)
                {
                    printf(",");
                }
                printf(s.c_str());
                pos++;
            }
            printf("]\n");
            return;
        }

        for(int j = i; j < n; j++)
        {
            if(isCorrect(str,i,j) == 1)
            {
                string sub = str.substr(i,j-i+1);
                path.push_back(sub);
                dfs(path, str, j+1);
                path.pop_back(); // 从子节点回退
            }
        }
    }
};



//int main()
//{
//    cout << "Hello World!" << endl;
//    Solution solution;
//    string s = "aab";
//    solution.partition(s);
//    cout << "End!" << endl;
//}
